package listNodePractice;

import java.lang.reflect.Array;
import java.util.*;

public class Class1019 {
    //TODO:2023/11/6  我自己想的
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> ans = new ArrayList<>();
        ListNode p = head;
//        LinkedList<Integer>  satck = new LinkedList<>();
//        satck.push(0);
//        p=p.next;
        while (p!=null){
            ListNode temp=p.next;
            while (temp!=null){
                if (temp.val>p.val){
                    ans.add(temp.val);
                    break;
                }else {
                    temp=temp.next;
                }
            }
            if (temp==null){
                ans.add(0);
            }
            p=p.next;
        }
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i]=ans.get(i);
        }
        return  res;


    }

    //TODO:2023/11/6   自己想着用单调栈但是不会没写出来  官方题解  栈里面存放数组
    class Solution {
        public int[] nextLargerNodes(ListNode head) {
//            List<Integer> ans = new ArrayList<Integer>();
//            Deque<int[]> stack = new ArrayDeque<int[]>();
//
//            ListNode cur = head;
//            int idx = -1;
//            while (cur != null) {
//                ++idx;
//                ans.add(0);
//                while (!stack.isEmpty() && stack.peek()[0] < cur.val) {
//                    ans.set(stack.pop()[1], cur.val);
//                }
//                stack.push(new int[]{cur.val, idx});
//                cur = cur.next;
//            }
//
//
//            int size = ans.size();
//            int[] arr = new int[size];
//            for (int i = 0; i < size; ++i) {
//                arr[i] = ans.get(i);
//            }
//            return arr;
             int[] ans=null;
            ArrayList<Integer> list = new ArrayList<>();
            LinkedList<int[]> stack = new LinkedList<>();
            ListNode cur=head;
            int id=-1;
            while (cur!=null){
                list.add(0);
                id++;
                //TODO:2023/11/8 很绝妙啊   维护的单调栈是递减的  只有满足最后一个元素比当前遍历的节点的数值大 就找到了
                while (!stack.isEmpty()&&stack.peek()[0]< cur.val){
                    list.add(stack.pop()[1], cur.val);
                }
                stack.push(new int[]{cur.val,id});
                cur=cur.next;
            }


            return  ans;

        }
    }





}
